10、砍竹子

题目 砍竹子

思路分析

贪心+暴力模拟

找到一颗最高的竹子 双指针检查左右是否有连续的一样高的 如果有 就全砍一次

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

LL h[N];

int n;

int main() {

    cin >> n;

    int ac=0;

    for (int i = 0; i < n; i++) {

        cin >> h[i];

        if(h[i]==1)

          ac++;

    }

    int cnt = 0;

    while (ac!=n) {

        // 找到最高的竹子

        LL max_height = 0;

        int idx = -1;

        for (int i = 0; i < n; i++) {

            if (h[i] > max_height) {

                max_height = h[i];

                idx = i;

            }

        }

        // 使用双指针找到连续相同高度的竹子

        int l = idx - 1, r = idx + 1;

        while (l >= 0 && h[l] == h[idx])

            l--;

        while (r < n && h[r] == h[idx])

            r++;

        // 对这些竹子使用魔法

        LL new_height = floor(sqrt(max_height / 2 + 1));

        for (int i = l + 1; i < r; i++){

           h[i] = new_height;

           if(new_height==1)

            ac++;

        }

        cnt++;

    }

    cout << cnt;

    return 0;

}

只能过4个 5分

时间花在了每次双指针找相同上

优化的思路是把相同高度的合并起来（记录l，r)

几个连续相同的是可以合并成一个的 这个技巧在岛屿那题见过

但是考试的时候可能想不到

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e5+10;

struct Seg{

    int l,r;

    LL v;

    bool operator<(const Seg& other)const{

        if(v!=other.v)

            return v<other.v;

        return l>other.l;

    }

};

priority_queue<Seg> heap;

LL h[N];

int n;

LL f(LL x)

{

    return sqrtl(x / 2 + 1);

}

int main()

{

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>h[i];

    for(int i=0;i<n;i++){

        int j=i+1;

        while(j<n && h[i]==h[j])

            j++;

        heap.push({i,j-1,h[i]});

        i=j-1;

    }

    int cnt=0;

    while (heap.size()>1 || heap.top().v>1) {

        auto cut = heap.top();

        heap.pop();

        while(heap.size() && heap.top().v == cut.v && cut.r + 1 == heap.top().l)

        {

            cut.r = heap.top().r;//相邻且等高的合并

            heap.pop();

        }

        heap.push({cut.l, cut.r, f(cut.v)});

        if (cut.v > 1)

            cnt++;

    }

    cout<<cnt;

    return 0;

}

同类题型

视频讲解

⬅️ 第十一届 c++ B组 省赛 🏠 00-刷题理模型 ➡️ 1、九进制转十进制